package demo4;

/**
 * 子数组系列
 *      环形子数组的最大和
 */
public class test2 {
    public int maxSubarraySumCircular(int[] nums) {
        // 创建dp表
        int n = nums.length;
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        // 初始化
        int sum = 0;
        int fmax = Integer.MIN_VALUE;
        int gmin = Integer.MAX_VALUE;

        for (int i = 1; i <= n; i++) {
            int x = nums[i-1];
            f[i] = Math.max(nums[i-1],f[i-1]+nums[i-1]);
            fmax = Math.max(fmax,f[i]);

            g[i] = Math.min(nums[i-1],g[i-1]+nums[i-1]);
            gmin = Math.min(gmin,g[i]);

            sum += x;
        }
        return sum == gmin? fmax : Math.max(fmax,sum-gmin);
    }
}
